package _01_array.mergesort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/4 - 18:32
 * 合并并排序两个数组
 */
public class MyTest {
    @Test
    public void test() {
        int[] arr = {1, 2, 3, 4};
        int[] arr2 = {1, 2, 3};

        int[] newArr = merge(arr, arr2);
        System.out.println(Arrays.toString(newArr));

        int[] a2 = new int[newArr.length];
        sort(newArr, 0, arr.length - 1, arr.length, newArr.length - 1, a2, 0);
        System.out.println(Arrays.toString(a2));

        int[] a3 = new int[newArr.length];
        sort2(newArr, 0, arr.length - 1, arr.length, newArr.length - 1, a3);
        System.out.println(Arrays.toString(a3));
    }

    private int[] merge(int[] arr, int[] arr2) {
        int[] newArr = new int[arr.length + arr2.length];
        System.arraycopy(arr, 0, newArr, 0, arr.length);
        System.arraycopy(arr2, 0, newArr, arr.length, arr2.length);
        return newArr;
    }

    /**
     * 排序数组
     * 新数组的有效排序长度，取决于最短区间的大小
     *
     * @param a1   源数组
     * @param i    第一区间开始下标
     * @param iEnd 第一区间结束下标
     * @param j    第二区间开始下标
     * @param jEnd 第二区间结束下标
     * @param a2   新数组
     * @param k    新插入位置
     */
    private void sort(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2, int k) {
        if (i > iEnd) {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        } else if (j > jEnd) {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        } else {
            if (a1[i] < a1[j]) {
                a2[k] = a1[i];
                sort(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
            } else {
                a2[k] = a1[j];
                sort(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
            }
        }
    }


    // 方式2 非递归
    private int[] sort2(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
        /*
            i
            1,2,3
            j
            2,4,5,6

                  i
            1,2,3
                j
            2,4,5,6
         */
        int k = 0;

        while (i <= iEnd && j <= jEnd) {
            if (a1[i] < a1[j]) {
                a2[k++] = a1[i++];
            } else {
                a2[k++] = a1[j++];
            }
        }
        if (i > iEnd) {
            System.arraycopy(a1, j, a2, k, jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(a1, i, a2, k, iEnd - i + 1);
        }
        return a2;
    }
}
